package com.coder.algorithm.offer_2;

import com.coder.algorithm.struct.ListNode;

import java.util.Locale;

/**
 * 合并两个排序的链表
 *
 * @author yuhushuan
 * @date 2020/6/18 11:57
 */
public class _25_1_MergeSortedLists {

    /**
     * 循环
     *
     * @param h1
     * @param h2
     * @return
     */
    private static ListNode merge(ListNode h1, ListNode h2) {
        if (h1 == null) {
            return h2;
        }
        if (h2 == null) {
            return h1;
        }
        ListNode p1 = h1;
        ListNode p2 = h2;

        ListNode head = null;
        ListNode min = null;

        while (p1 != null && p2 != null) {
            if (p1.getValue() <= p2.getValue()) {
                if (min != null) {
                    min.setNext(p1);
                }
                min = p1;
                p1 = p1.getNext();
            } else {
                if (min != null) {
                    min.setNext(p2);
                }
                min = p2;
                p2 = p2.getNext();
            }
            if (head == null) {
                head = min;
            }
        }
        if (p1 == null) {
            min.setNext(p2);
        }
        if (p2 == null) {
            min.setNext(p1);
        }
        return head;
    }

    /**
     * 递归实现
     *
     * @param h1
     * @param h2
     * @return
     */
    private static ListNode merge_Recursively(ListNode h1, ListNode h2) {
        if (h1 == null) {
            return h2;
        }
        if (h2 == null) {
            return h1;
        }
        // 获取较小的节点作为头节点
        ListNode head = null;
        if (h1.getValue() <= h2.getValue()) {
            head = h1;
            h1 = h1.getNext();
        } else {
            head = h2;
            h2 = h2.getNext();
        }
        head.setNext(merge_Recursively(h1, h2));
        return head;
    }

    public static void main(String[] args) {
        // 功能测试
        // 两个链表有多个节点，节点值互不相同
        test1();
        // 两个链表有多个节点，节点值存在相同
        test1_1();

        // 特殊输入测试
        // 两个链表一个为 null
        test2();
        test3();
        // 两个链表都为 null
        print(null, null);
        // 两个链表只有一个节点
        test4();


    }

    private static void test1() {
        ListNode n1 = ListNode.Companion.create(new int[]{1, 3, 5, 7});
        ListNode n2 = ListNode.Companion.create(new int[]{2,4,6,8});

        print(n1, n2);
    }

    private static void test1_1() {
        ListNode n1 = ListNode.Companion.create(new int[]{1, 3, 7});
        ListNode n2 = ListNode.Companion.create(new int[]{2, 3, 4, 8});

        print(n1, n2);
    }

    private static void test2() {
        ListNode n1 = ListNode.Companion.create(new int[]{1, 3, 5, 7});

        print(n1, null);
    }

    private static void test3() {
        ListNode n1 = ListNode.Companion.create(new int[]{1, 3, 5, 7});

        print(null, n1);
    }

    private static void test4() {
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);


        print(n1, n2);
    }

    private static void print(ListNode h1, ListNode h2) {
        System.out.println(String.format(Locale.getDefault(),
                "链表 1：%s\n链表 2：%s\n合并后：\n%s\n",
                ListNode.Companion.toList(h1), ListNode.Companion.toList(h2), ListNode.Companion.toList(merge_Recursively(h1, h2))));
    }
}
